/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 晓星航
 * Date: 2023-12-22
 * Time: 18:30
 */
public class MazeDFS {
    // 定义迷宫大小
    private static final int M = 8;
    private static final int N = 8;
    // 定义迷宫地图，0表示可以通过，1表示障碍物
    private static final int[][] MAP = {
            {0, 0, 0, 0, 0, 0, 0, 0},
            {0, 1, 1, 1, 0, 1, 1, 0},
            {0, 0, 0, 0, 0, 1, 1, 0},
            {0, 1, 0, 1, 1, 1, 0, 1},
            {0, 1, 0, 0, 0, 0, 0, 0},
            {0, 1, 1, 1, 1, 0, 1, 0},
            {0, 0, 0, 0, 1, 0, 0, 0},
            {0, 1, 1, 1, 0, 0, 1, 0}
    };
    // 定义起点和终点坐标
    private static final int START_X = 1;
    private static final int START_Y = 1;
    private static final int END_X = 6;
    private static final int END_Y = 6;

    public static void dfs(int x, int y) {
        if (x == END_X && y == END_Y) { // 到达终点，输出路径
            for (int i = 0; i < M; i++) {
                for (int j = 0; j < N; j++) {
                    System.out.print(MAP[i][j] + " ");
                }
                System.out.println();
            }
            System.out.println("------------------");
            return;
        }
        if (MAP[x][y] == 0) { // 当前位置可以通过
            MAP[x][y] = 2; // 标记为已经走过
            // 向四个方向继续搜索
            dfs(x + 1, y);
            dfs(x, y + 1);
            dfs(x - 1, y);
            dfs(x, y - 1);
            MAP[x][y] = 0; // 回溯，标记为未走过
        }
        System.out.println("搜索完成！");
    }
    public static void main(String[] args) {
        dfs(START_X, START_Y); // 从起点开始搜索
    }
}

